#include "OctreeConstructor.h"
#include <time.h>
#include <sstream>
#define GROUP_SIZE 64
#define SORT_BUF_W 1024
#define SORT_BUF_H 256
#define SORT_BUFFER_SIZE SORT_BUF_W * SORT_BUF_H

#ifdef QUERY_TIME
// #define OCTREE_QUERY_TIME
#endif
#ifdef OCTREE_QUERY_TIME
#define CALL_QUERY_TIME(__str__) timeQuery.addCheckPoint (__str__)
#define GET_DURATION(__name__) \
	timeQuery.getDuration ( \
			std::string (__name__) + "Start", \
			std::string (__name__) + "End")
#define OUTPUT_DURATION(__stream__, __name__) \
	sOut << __name__ << ": " << GET_DURATION (__name__) << "ms\n"
#else
#define CALL_QUERY_TIME(__str__)
#endif

#define QUERY_METHOD(__method__, __name__) \
	CALL_QUERY_TIME (std::string (__name__) + "Start"); \
	__method__ (); \
	CALL_QUERY_TIME (std::string (__name__) + "End")



struct Info
{
	uint dispatchNum[3]; // 0 - 2
	int level; // 3
};

#define DISPATCH_SIZE "asuint (g_info.Load (0))"
#define LEVEL "asint (g_info.Load (12))"


struct SimpleNode
{
	SimpleNode ()
	{
		memset (this, 0xFFFFFFFF, sizeof (SimpleNode));
		int verticesNum = 0;
	}
	UINT key;
	int verticesBaseIdx;
	int verticesNum;
};


UINT LUT[16][27] = {
	{ 0, 1, 1, 3, 4, 4, 3, 4, 4, 9, 10, 10, 12, 13, 13, 12, 13, 13, 9, 10, 10, 12, 13, 13, 12, 13, 13 },
	{ 1, 1, 2, 4, 4, 5, 4, 4, 5, 10, 10, 11, 13, 13, 14, 13, 13, 14, 10, 10, 11, 13, 13, 14, 13, 13, 14 },
	{ 3, 4, 4, 3, 4, 4, 6, 7, 7, 12, 13, 13, 12, 13, 13, 15, 16, 16, 12, 13, 13, 12, 13, 13, 15, 16, 16 },
	{ 4, 4, 5, 4, 4, 5, 7, 7, 8, 13, 13, 14, 13, 13, 14, 16, 16, 17, 13, 13, 14, 13, 13, 14, 16, 16, 17 },
	{ 9, 10, 10, 12, 13, 13, 12, 13, 13, 9, 10, 10, 12, 13, 13, 12, 13, 13, 18, 19, 19, 21, 22, 22, 21, 22, 22 },
	{ 10, 10, 11, 13, 13, 14, 13, 13, 14, 10, 10, 11, 13, 13, 14, 13, 13, 14, 19, 19, 20, 22, 22, 23, 22, 22, 23 },
	{ 12, 13, 13, 12, 13, 13, 15, 16, 16, 12, 13, 13, 12, 13, 13, 15, 16, 16, 21, 22, 22, 21, 22, 22, 24, 25, 25 },
	{ 13, 13, 14, 13, 13, 14, 16, 16, 17, 13, 13, 14, 13, 13, 14, 16, 16, 17, 22, 22, 23, 22, 22, 23, 25, 25, 26 },
	{ 7, 6, 7, 5, 4, 5, 7, 6, 7, 3, 2, 3, 1, 0, 1, 3, 2, 3, 7, 6, 7, 5, 4, 5, 7, 6, 7 },
	{ 6, 7, 6, 4, 5, 4, 6, 7, 6, 2, 3, 2, 0, 1, 0, 2, 3, 2, 6, 7, 6, 4, 5, 4, 6, 7, 6 },
	{ 5, 4, 5, 7, 6, 7, 5, 4, 5, 1, 0, 1, 3, 2, 3, 1, 0, 1, 5, 4, 5, 7, 6, 7, 5, 4, 5 },
	{ 4, 5, 4, 6, 7, 6, 4, 5, 4, 0, 1, 0, 2, 3, 2, 0, 1, 0, 4, 5, 4, 6, 7, 6, 4, 5, 4 },
	{ 3, 2, 3, 1, 0, 1, 3, 2, 3, 7, 6, 7, 5, 4, 5, 7, 6, 7, 3, 2, 3, 1, 0, 1, 3, 2, 3 },
	{ 2, 3, 2, 0, 1, 0, 2, 3, 2, 6, 7, 6, 4, 5, 4, 6, 7, 6, 2, 3, 2, 0, 1, 0, 2, 3, 2 },
	{ 1, 0, 1, 3, 2, 3, 1, 0, 1, 5, 4, 5, 7, 6, 7, 5, 4, 5, 1, 0, 1, 3, 2, 3, 1, 0, 1 },
	{ 0, 1, 0, 2, 3, 2, 0, 1, 0, 4, 5, 4, 6, 7, 6, 4, 5, 4, 0, 1, 0, 2, 3, 2, 0, 1, 0 }
};
UINT neighborsShareTheVertexTable[8][8] = {
	{ 0, 1, 3, 4, 9, 10, 12, 13 },
	{ 1, 2, 4, 5, 10, 11, 13, 14 },
	{ 3, 4, 6, 7, 12, 13, 15, 16 },
	{ 4, 5, 7, 8, 13, 14, 16, 17 },
	{ 9, 10, 12, 13, 18, 19, 21, 22 },
	{ 10, 11, 13, 14, 19, 20, 22, 23 },
	{ 12, 13, 15, 16, 21, 22, 24, 25 },
	{ 13, 14, 16, 17, 22, 23, 25, 26 }
};

UINT neighborsShareTheEdgeTable[12][4] = {
	{ 1, 4, 10, 13 }, { 4, 7, 13, 16 }, { 10, 13, 19, 22 }, { 13, 16, 22, 25 },
	{ 3, 4, 12, 13 }, { 4, 5, 13, 14 }, { 12, 13, 21, 22 }, { 13, 14, 22, 23 },
	{ 9, 10, 12, 13 }, { 10, 11, 13, 14 }, { 12, 13, 15, 16 }, { 13, 14, 16, 17 }
};

UINT vertexShareTheEdgeTable[12][2] = {
	{ 0, 1 }, { 2, 3 }, { 4, 5 }, { 6, 7 },
	{ 0, 2 }, { 1, 3 }, { 4, 6 }, { 5, 7 },
	{ 0, 4 }, { 1, 5 }, { 2, 6 }, { 3, 7 },
};

struct LUTStruct {

	LUTStruct ()
	{
		memcpy (table1, LUT, 16 * 27 * sizeof (UINT));
		memcpy (table2, neighborsShareTheVertexTable, 8 * 8 * sizeof (UINT));
		memcpy (table3, neighborsShareTheEdgeTable, 12 * 4 * sizeof (UINT));
		memcpy (table4, vertexShareTheEdgeTable, 12 * 2 * sizeof (UINT));
	}

	UINT table1[16][27];
	UINT table2[8][8];
	UINT table3[12][4];
	UINT table4[12][2];
};

#define PARENT_TABLE_OFFSET "0"
#define CHILD_TABLE_OFFSET "216"
#define VERTEX_TABLE_OFFSET "432"
#define EDGE_TABLE_OFFSET "496"
#define EDGE_VERTEX_TABLE_OFFSET "544"


OctreeConstructor::OctreeConstructor ()
{
}


OctreeConstructor::~OctreeConstructor ()
{
}

void OctreeConstructor::initial (Octree *p_octree)
{

	UINT elemNum = p_octree->structInfo.var.elemNum;
	if (SORT_BUFFER_SIZE < elemNum)
		throw std::exception ("OctreeConstructor::OctreeConstructor(): "
				"Sort buffer is too small.");

	QD3DUtils d3DUtils;

	_p_mainIdxHintDxConstBuf = d3DUtils.createConstBuffer ((MainIdxHint*)NULL);

	Info infoInitData = { elemNum / GROUP_SIZE, 1, 1, -1 };
	CD3D11_BUFFER_DESC infoBufdesc;
	ZeroMemory (&infoBufdesc, sizeof (CD3D11_BUFFER_DESC));
	infoBufdesc.BindFlags = D3D11_BIND_SHADER_RESOURCE |
			D3D11_BIND_UNORDERED_ACCESS;
	infoBufdesc.ByteWidth = sizeof (Info);
	infoBufdesc.MiscFlags = D3D11_RESOURCE_MISC_DRAWINDIRECT_ARGS |
			D3D11_RESOURCE_MISC_BUFFER_ALLOW_RAW_VIEWS;
	ID3D11Buffer *p_infoDxBuf = d3DUtils.createBuffer (infoBufdesc,
			(void *)&infoInitData);
	_p_infoPack = new QD3DResourcePack (p_infoDxBuf);

	LUTStruct lut;
	ID3D11Buffer *p_tableDxBuf = d3DUtils.createStructuredBuffer (
			sizeof(lut) / sizeof(UINT), (UINT*)&lut,
			D3D11_BIND_SHADER_RESOURCE);
	_p_tablePack = new QD3DResourcePack (p_tableDxBuf, QD3DResourcePack::SRV);

	glm::uvec2 *keysBufInitData = new glm::uvec2[SORT_BUFFER_SIZE];
	memset (&keysBufInitData[0], -1, sizeof (glm::uvec2) * SORT_BUFFER_SIZE);
	
	ID3D11Buffer *p_emptyKeysDxBuf = d3DUtils.createStructuredBuffer (
			elemNum, (glm::uvec2*)keysBufInitData,
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_emptyKeysPack = new QD3DResourcePack (p_emptyKeysDxBuf);

	ID3D11Buffer *p_unsortedKeysDxBuf = d3DUtils.createStructuredBuffer (
			SORT_BUFFER_SIZE, (glm::uvec2*)keysBufInitData,
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_unsortedKeysPack = new QD3DResourcePack (p_unsortedKeysDxBuf);

	ID3D11Buffer *p_keysDxBuf = d3DUtils.createStructuredBuffer (
			elemNum, (glm::uvec2*)keysBufInitData,
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_keysPack = new QD3DResourcePack (p_keysDxBuf);

	ID3D11Buffer *p_compactedKeysDxBuf = d3DUtils.createStructuredBuffer (
			elemNum, (glm::uvec2*)keysBufInitData,
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_compactedKeysPack = new QD3DResourcePack (p_compactedKeysDxBuf);

	delete [] keysBufInitData;
	keysBufInitData = NULL;


	UINT *marksBufInitData = new UINT[elemNum];
	memset (&marksBufInitData[0], 0, sizeof (UINT) * elemNum);
	ID3D11Buffer *p_emptyMarksDxBuf = d3DUtils.createStructuredBuffer (
			elemNum, marksBufInitData,
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_emptyMarksPack = new QD3DResourcePack (p_emptyMarksDxBuf);
	ID3D11Buffer *p_marksDxBuf = d3DUtils.createStructuredBuffer (
			elemNum, marksBufInitData,
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_marksPack = new QD3DResourcePack (p_marksDxBuf);
	delete [] marksBufInitData;
	marksBufInitData = NULL;

	int addrsBufSize = elemNum * 8;
	int *addrsBufInitData = new int[addrsBufSize];
	memset (&addrsBufInitData[0], -1, sizeof (int) * addrsBufSize);
	ID3D11Buffer *p_addrsDxBuf = d3DUtils.createStructuredBuffer (
			addrsBufSize, addrsBufInitData,
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_addrsPack = new QD3DResourcePack (p_addrsDxBuf);
	delete [] addrsBufInitData;
	addrsBufInitData = NULL;

	QVector< SimpleNode > nodesBufInitData (elemNum);
	ID3D11Buffer *p_emptyNodesDxBuf = d3DUtils.createStructuredBuffer (
			elemNum, &nodesBufInitData[0],
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_emptyNodesPack = new QD3DResourcePack (p_emptyNodesDxBuf);
	ID3D11Buffer *p_nodesDxBuf = d3DUtils.createStructuredBuffer (
			elemNum, &nodesBufInitData[0],
			D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_UNORDERED_ACCESS);
	_p_nodesPack = new QD3DResourcePack (p_nodesDxBuf);

	QD3DShaderDesc shaderDesc;
	std::ostringstream sOut;
	sOut << GROUP_SIZE;
	shaderDesc.setDefine ("GROUP_SIZE", sOut.str ());
	sOut = std::ostringstream ();
	sOut << elemNum;
	shaderDesc.setDefine ("NUM_ELEMENTS", sOut.str ());
	shaderDesc.setDefine ("DISPATCH_SIZE", DISPATCH_SIZE);
	shaderDesc.setDefine ("LEVEL", LEVEL);
	shaderDesc.setDefine ("VERTEX_STRUCT", VERTEX_HLSL_STRUCT);
	shaderDesc.setDefine ("NODE_STRUCT", Octree::Node::s_HLSL_STRUCT_STR);
	_p_updateInfoInConstructNodesCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\UpdateInfoCS.hlsl",
			"inConstructNodes", shaderDesc);
	_p_calcKeyCS = d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\CalcKeyCS.hlsl",
			"csMain", shaderDesc);
	_p_genSortedVerticesAndKeysCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\GenSortedVerticesAndKeysCS.hlsl",
			"csMain", shaderDesc);
	_p_markUniqueCS = d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\MarkUniqueCS.hlsl",
			"csMain", shaderDesc);
	_p_genNodesAndMarkUniqueParentCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\GenNodesAndMarkCS.hlsl",
			"csMain", shaderDesc);
	_p_adjustAddrsAndUpdateKeysCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\AdjustAddrsAndUpdateKeysCS.hlsl",
			"csMain", shaderDesc);
	_p_fillFinalNodesCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\FillFinalNodesCS.hlsl",
			"csMain", shaderDesc);
	_p_connectParentChildrenCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\ConnectParentChildrenCS.hlsl",
			"csMain", shaderDesc);

	sOut = std::ostringstream ();
	sOut << GROUP_SIZE / 2;
	shaderDesc.setDefine ("GROUP_SIZE", sOut.str ());
	shaderDesc.setDefine ("PARENT_TABLE_OFFSET", PARENT_TABLE_OFFSET);
	shaderDesc.setDefine ("CHILD_TABLE_OFFSET", CHILD_TABLE_OFFSET);
	shaderDesc.setDefine ("VERTEX_TABLE_OFFSET", VERTEX_TABLE_OFFSET);
	shaderDesc.setDefine ("EDGE_TABLE_OFFSET", EDGE_TABLE_OFFSET);
	shaderDesc.setDefine ("EDGE_VERTEX_TABLE_OFFSET", EDGE_VERTEX_TABLE_OFFSET);
	shaderDesc.setDefine ("NODE_VERTEX_STRUCT", Octree::NodeVertex::s_HLSL_STRUCT_STR);
	shaderDesc.setDefine ("NODE_EDGE_STRUCT", Octree::NodeEdge::s_HLSL_STRUCT_STR);
	_p_updateInfoInConnectNeighborsCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\UpdateInfoCS.hlsl",
			"inConnectNeighbors", shaderDesc);
	_p_connectNeighborsCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\ConnectNeighborsCS.hlsl",
			"nonrootLevel", shaderDesc);
	_p_connectRootNeighborsCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\ConnectNeighborsCS.hlsl",
			"rootLevel", shaderDesc);
	_p_genNodeVerticesCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\GenNodeGridInfoCS.hlsl",
			"genVertices", shaderDesc);
	_p_genNodeEdgesCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\GenNodeGridInfoCS.hlsl",
			"genEdges", shaderDesc);

	sOut = std::ostringstream ();
	sOut << GROUP_SIZE;
	shaderDesc.setDefine ("GROUP_SIZE", sOut.str ());
	_p_clearOctreeNodesCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\ClearOctreeCS.hlsl",
			"clearNodes", shaderDesc);
	_p_clearOctreeNodeVerticesCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\ClearOctreeCS.hlsl",
			"clearVertices", shaderDesc);
	_p_clearOctreeNodeEdgesCS =
			d3DUtils.createShaderFromFile< ID3D11ComputeShader > (
			QD3DUtils::COMPUTE_SHADER, "cs_5_0",
			"..\\Data\\Shaders\\Octree\\ClearOctreeCS.hlsl",
			"clearEdges", shaderDesc);

	_p_sortPrimitive = new SortPrimitive (
			glm::uvec2 (SORT_BUF_W, SORT_BUF_H), _p_unsortedKeysPack,
			sizeof (glm::uvec2), "uint2");

	_p_compactPrimitive = new CompactPrimitive (elemNum,
			_p_keysPack, _p_marksPack, _p_compactedKeysPack, "uint2");
}

void OctreeConstructor::process (Octree *p_octree,
		QD3DResourcePack *p_verticesPack)
{
	_rp_octree = p_octree;
	_rp_verticesPack = p_verticesPack;

	QD3DUtils d3DUtils;
	int maxLevel = _rp_octree->structInfo.var.maxLevel;

#ifdef OCTREE_QUERY_TIME
	QD3DTimeQuery timeQuery;
	timeQuery.begin ();
	timeQuery.addCheckPoint ("Start");
#endif

	// Preprocess
	QUERY_METHOD (_generateKeys, "GenerateKeys");
	QUERY_METHOD (_sortKeysAndVertices, "Sort");
	QUERY_METHOD (_markUnique, "Mark");
	QUERY_METHOD (_compactKeys, "Compact");
	QUERY_METHOD (_adjustAddrsAndUpdateKeys, "AdjustUpdate");

	char strLevel[2] = { '0', '\0' };
	for (int l = 0; l < maxLevel; ++l, ++strLevel[0]) {
#ifdef OCTREE_QUERY_TIME
		timeQuery.addCheckPoint (std::string("ConstructNodesLevel(") + strLevel + ")Start");
#endif
		QUERY_METHOD (_updateInfoInConstructNodes, std::string("UpdateInfoInConstructNodes(") + strLevel + ")");
		QUERY_METHOD (_resetBufs, std::string("ResetBuffer(") + strLevel + ")");
		QUERY_METHOD (_genNodesAndMarkUniqueParent, std::string("GenMark(") + strLevel + ")");
		QUERY_METHOD (_compactKeys, std::string("Compact(") + strLevel + ")");
		QUERY_METHOD (_adjustAddrsAndUpdateKeys, std::string("AdjustUpdate(") + strLevel + ")");
		if (l != 0) {
			QUERY_METHOD(_connectParentChildren, std::string("Connect(") + strLevel + ")");
		}
		QUERY_METHOD (_fillFinalNodes, std::string("Fill(") + strLevel + ")");
#ifdef OCTREE_QUERY_TIME
		timeQuery.addCheckPoint (std::string("ConstructNodesLevel(") + strLevel + ")End");
#endif
	}

	QUERY_METHOD (_connectRootNeighbors, "ConnectRootNeighbors");
	strLevel[0] -= 2;
	for (int l = maxLevel - 2; l >= 0; --l, --strLevel[0]) {
#ifdef OCTREE_QUERY_TIME
		timeQuery.addCheckPoint (std::string("ConnectNeighborsLevel(") + strLevel + ")Start");
#endif
		QUERY_METHOD (_updateInfoInConnectNeighbors, std::string("UpdateInfoConnectNeighbors(") + strLevel + ")");
		QUERY_METHOD (_connectNeighbors, std::string("ConnectNeighbors(") + strLevel + ")");
#ifdef OCTREE_QUERY_TIME
		timeQuery.addCheckPoint (std::string("ConnectNeighborsLevel(") + strLevel + ")End");
#endif
	}
	
	QUERY_METHOD (_genNodeVertices, "GenNodeVertices");
	QUERY_METHOD (_genNodeEdges, "GenNodeEdges");

	Info infoInitData = { _rp_octree->structInfo.var.elemNum / GROUP_SIZE, 1, 1, -1 };
	d3DUtils.updateSubresource (_p_infoPack->getRes (), 0, &infoInitData);

#ifdef OCTREE_QUERY_TIME
	timeQuery.addCheckPoint ("End");
	timeQuery.end ();

	std::ostringstream sOut;
	sOut << "######################################################" << std::endl;
	sOut << "# All: " << GET_DURATION ("") << "ms\n";
	sOut << "######################################################" << std::endl;
	OUTPUT_DURATION (sOut, "GenerateKeys");
	OUTPUT_DURATION (sOut, "Sort");
	OUTPUT_DURATION (sOut, "Mark");
	OUTPUT_DURATION (sOut, "Compact");
	OUTPUT_DURATION (sOut, "AdjustUpdate");
	strLevel[0] = '0';
	for (int l = 0; l < maxLevel; ++l, ++strLevel[0]) {
		sOut << "======================================================" << std::endl;
		OUTPUT_DURATION (sOut, std::string("ConstructNodesLevel(") + strLevel + ")");
		OUTPUT_DURATION (sOut, std::string("UpdateInfoInConstructNodes(") + strLevel + ")");
		OUTPUT_DURATION (sOut, std::string("ResetBuffer(") + strLevel + ")");
		OUTPUT_DURATION (sOut, std::string("GenMark(") + strLevel + ")");
		OUTPUT_DURATION (sOut, std::string("Compact(") + strLevel + ")");
		OUTPUT_DURATION (sOut, std::string("AdjustUpdate(") + strLevel + ")");
		if (l != 0) {
			OUTPUT_DURATION(sOut, std::string("Connect(") + strLevel + ")");
		}
		OUTPUT_DURATION (sOut, std::string("Fill(") + strLevel + ")");
	}
	sOut << "======================================================" << std::endl;
	sOut << "======================================================" << std::endl;
	OUTPUT_DURATION (sOut, "ConnectRootNeighbors");
	strLevel[0] -= 2;
	for (int l = maxLevel - 2; l >= 0; --l, --strLevel[0]) {
		sOut << "======================================================" << std::endl;
		OUTPUT_DURATION (sOut, std::string("ConnectNeighborsLevel(") + strLevel + ")");
		OUTPUT_DURATION (sOut, std::string("UpdateInfoConnectNeighbors(") + strLevel + ")");
		OUTPUT_DURATION (sOut, std::string("ConnectNeighbors(") + strLevel + ")");
	}
	sOut << "======================================================" << std::endl;
	sOut << "======================================================" << std::endl;
	OUTPUT_DURATION (sOut, "GenNodeVertices");
	OUTPUT_DURATION (sOut, "GenNodeEdges");
	OutputDebugStringA (sOut.str ().c_str ());
#endif
}

void OctreeConstructor::clean ()
{
}

void OctreeConstructor::_generateKeys ()
{
	QD3DUtils d3DUtils;

	QVector< ID3D11Buffer * > dxConstBufPtrs (1);
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (1);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (1);

	dxConstBufPtrs[0] = _rp_octree->p_octreeInfoDxConstBuf;
	d3DUtils.setConstBufs (QD3DUtils::COMPUTE_SHADER, 0, dxConstBufPtrs);
	dxSRVPtrs[0] = _rp_verticesPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _p_unsortedKeysPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_calcKeyCS);
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearConstBufs (QD3DUtils::COMPUTE_SHADER, 0, dxConstBufPtrs.size ());
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_sortKeysAndVertices ()
{
	_p_sortPrimitive->run ();

	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (1);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (3);

	dxSRVPtrs[0] = _rp_verticesPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _rp_octree->p_verticesPack->getUAV ();
	dxUAVPtrs[1] = _p_keysPack->getUAV ();
	dxUAVPtrs[2] = _p_unsortedKeysPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_genSortedVerticesAndKeysCS);
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_markUnique ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (1);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (1);

	dxSRVPtrs[0] = _p_keysPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _p_marksPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_markUniqueCS);
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_compactKeys ()
{
	QD3DUtils d3DUtils;
	_p_compactPrimitive->run ();
	d3DUtils.copyResource (_p_keysPack->getRes (),
			_p_compactedKeysPack->getRes ());
	// Clear compacted keys array
	d3DUtils.copyResource (_p_compactedKeysPack->getRes (),
			_p_emptyKeysPack->getRes ());
}

void OctreeConstructor::_adjustAddrsAndUpdateKeys ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (1);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (2);

	dxSRVPtrs[0] = _p_infoPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _p_marksPack->getUAV ();
	dxUAVPtrs[1] = _p_keysPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_adjustAddrsAndUpdateKeysCS);
	
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_genNodesAndMarkUniqueParent ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (2);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (2);

	dxSRVPtrs[0] = _p_keysPack->getSRV ();
	dxSRVPtrs[1] = _p_infoPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _p_nodesPack->getUAV ();
	dxUAVPtrs[1] = _p_marksPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_genNodesAndMarkUniqueParentCS);
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_fillFinalNodes ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (4);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (2);

	dxSRVPtrs[0] = _p_infoPack->getSRV ();
	dxSRVPtrs[1] = _p_nodesPack->getSRV ();
	dxSRVPtrs[2] = _p_marksPack->getSRV ();
	dxSRVPtrs[3] = _rp_octree->p_levelPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _rp_octree->p_nodesPack->getUAV ();
	dxUAVPtrs[1] = _p_addrsPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_fillFinalNodesCS);
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());

	// Clear nodes array
	d3DUtils.copyResource (_p_nodesPack->getRes (),
			_p_emptyNodesPack->getRes ());

}

void OctreeConstructor::_connectParentChildren ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (2);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (2);

	dxSRVPtrs[0] = _p_infoPack->getSRV ();
	dxSRVPtrs[1] = _rp_octree->p_levelPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _rp_octree->p_nodesPack->getUAV ();
	dxUAVPtrs[1] = _p_addrsPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_connectParentChildrenCS);
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_updateInfoInConstructNodes ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (1);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (2);

	dxSRVPtrs[0] = _p_marksPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _p_infoPack->getUAV ();
	dxUAVPtrs[1] = _rp_octree->p_levelPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_updateInfoInConstructNodesCS);
	d3DUtils.dispatch (1, 1, 1);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_resetBufs ()
{
	QD3DUtils d3DUtils;

	// Clear marks array
	d3DUtils.copyResource (_p_marksPack->getRes (),
			_p_emptyMarksPack->getRes ());

}

void OctreeConstructor::_updateInfoInConnectNeighbors ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (1);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (2);

	dxSRVPtrs[0] = _p_marksPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _p_infoPack->getUAV ();
	dxUAVPtrs[1] = _rp_octree->p_levelPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_updateInfoInConnectNeighborsCS);
	d3DUtils.dispatch (1, 1, 1);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_connectNeighbors ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (4);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (1);

	dxSRVPtrs[0] = _p_infoPack->getSRV ();
	dxSRVPtrs[1] = _rp_octree->p_levelPack->getSRV ();
	dxSRVPtrs[2] = _p_addrsPack->getSRV ();
	dxSRVPtrs[3] = _p_tablePack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _rp_octree->p_nodesPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_connectNeighborsCS);
	d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_connectRootNeighbors ()
{
	QD3DUtils d3DUtils;
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (4);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (1);

	dxSRVPtrs[0] = _p_infoPack->getSRV ();
	dxSRVPtrs[1] = _rp_octree->p_levelPack->getSRV ();
	dxSRVPtrs[2] = _p_addrsPack->getSRV ();
	dxSRVPtrs[3] = _p_tablePack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _rp_octree->p_nodesPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_connectRootNeighborsCS);
	d3DUtils.dispatch (1, 1, 1);
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_genNodeVertices ()
{
	QD3DUtils d3DUtils;
	MainIdxHint constVars;

	QVector< ID3D11Buffer * > dxConstBufPtrs (2);
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (3);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (3);

	dxConstBufPtrs[0] = _p_mainIdxHintDxConstBuf;
	dxConstBufPtrs[1] = _rp_octree->p_octreeInfoDxConstBuf;
	d3DUtils.setConstBufs (QD3DUtils::COMPUTE_SHADER, 0, dxConstBufPtrs);
	dxSRVPtrs[0] = _rp_octree->p_levelPack->getSRV ();
	dxSRVPtrs[1] = _p_tablePack->getSRV ();
	dxSRVPtrs[2] = _rp_octree->p_verticesPack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _rp_octree->p_nodesPack->getUAV ();
	dxUAVPtrs[1] = _rp_octree->p_nodeVerticesPack->getUAV ();
	dxUAVPtrs[2] = _rp_octree->p_nodeEdgesPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_genNodeVerticesCS);
	for (int i = 0; i < 8; ++i) {
		constVars.var.mainIdx = i;
		d3DUtils.updateSubresource (_p_mainIdxHintDxConstBuf, 0, &constVars);
		d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	}
	d3DUtils.clearConstBufs (QD3DUtils::COMPUTE_SHADER, 0, dxConstBufPtrs.size ());
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::_genNodeEdges ()
{
	QD3DUtils d3DUtils;
	MainIdxHint constVars;

	QVector< ID3D11Buffer * > dxConstBufPtrs (2);
	QVector< ID3D11ShaderResourceView * > dxSRVPtrs (2);
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (3);

	dxConstBufPtrs[0] = _p_mainIdxHintDxConstBuf;
	dxConstBufPtrs[1] = _rp_octree->p_octreeInfoDxConstBuf;
	d3DUtils.setConstBufs (QD3DUtils::COMPUTE_SHADER, 0, dxConstBufPtrs);
	dxSRVPtrs[0] = _rp_octree->p_levelPack->getSRV ();
	dxSRVPtrs[1] = _p_tablePack->getSRV ();
	d3DUtils.setSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs);
	dxUAVPtrs[0] = _rp_octree->p_nodesPack->getUAV ();
	dxUAVPtrs[1] = _rp_octree->p_nodeVerticesPack->getUAV ();
	dxUAVPtrs[2] = _rp_octree->p_nodeEdgesPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_genNodeEdgesCS);
	for (int i = 0; i < 4; ++i) {
		constVars.var.mainIdx = i;
		d3DUtils.updateSubresource (_p_mainIdxHintDxConstBuf, 0, &constVars);
		d3DUtils.indirectDispatch ((ID3D11Buffer*)_p_infoPack->getRes (), 0);
	}
	d3DUtils.clearConstBufs (QD3DUtils::COMPUTE_SHADER, 0, dxConstBufPtrs.size ());
	d3DUtils.clearSRVs (QD3DUtils::COMPUTE_SHADER, 0, dxSRVPtrs.size ());
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}

void OctreeConstructor::clearOctree (Octree *p_octree)
{
	QD3DUtils d3DUtils;
	QVector< ID3D11UnorderedAccessView * > dxUAVPtrs (3);

	dxUAVPtrs[0] = p_octree->p_nodesPack->getUAV ();
	dxUAVPtrs[1] = p_octree->p_nodeVerticesPack->getUAV ();
	dxUAVPtrs[2] = p_octree->p_nodeEdgesPack->getUAV ();
	d3DUtils.setUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs);

	d3DUtils.setComputeShader (_p_clearOctreeNodesCS);
	d3DUtils.dispatch (p_octree->structInfo.var.elemNum / GROUP_SIZE, 1, 1);
	d3DUtils.setComputeShader (_p_clearOctreeNodeVerticesCS);
	d3DUtils.dispatch (p_octree->structInfo.var.elemNum / GROUP_SIZE, 1, 1);
	d3DUtils.setComputeShader (_p_clearOctreeNodeEdgesCS);
	d3DUtils.dispatch (p_octree->structInfo.var.elemNum / GROUP_SIZE, 1, 1);
	d3DUtils.clearUAVs (QD3DUtils::COMPUTE_SHADER, 0, dxUAVPtrs.size ());
}